package com.jeff.practice;

/**
 * 接雨水问题
 * 使用双指针从左右两侧进行比较，计算可以接的雨水量。
 * 在左侧和右侧分别存在更高的柱子时，可以确定当前位置的雨水量。
 */
public class TrappingRainWater {

    public static void main(String[] args) {
        int[] heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int rainWater = trap(heights);
        System.out.println("接住的雨水量: " + rainWater); // 输出: 6
    }

    public static int trap(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        // 初始化
        int left = 0, right = heights.length - 1;
        int leftMax = 0, rightMax = 0;
        int waterTrapped = 0;

        while (left < right) {
            if (heights[left] < heights[right]) {
                // 处理左边
                if (heights[left] >= leftMax) {
                    leftMax = heights[left]; // 更新左边最大高度
                } else {
                    waterTrapped += leftMax - heights[left]; // 计算可以接的水
                }
                left++;
            } else {
                // 处理右边
                if (heights[right] >= rightMax) {
                    rightMax = heights[right]; // 更新右边最大高度
                } else {
                    waterTrapped += rightMax - heights[right]; // 计算可以接的水
                }
                right--;
            }
        }

        return waterTrapped;
    }
}
